#define _CRT_SECURE_NO_WARNINGS 1

/*
给定两个数，求这两个数的最大公约数
例如：
输入：20 40
输出：20
*/
#include<stdio.h>

int gcd(int a, int b)
{
	if (a < b)
	{
		int temp = a;
		a = b;
		b = temp;
	}

	while (b != 0 && a > b)
	{
		int temp = a % b;
		a = b;
		b = temp;
	}
	return a;

}

int main()
{
	int a, b;
	scanf_s("%d%d", &a, &b);
	printf("%d\n", gcd(a, b));

	return 0;
}


///*
//方法一：辗转相除法（欧几里得算法）
//
//辗转相除法是一种用于计算两个数的最大公约数的经典算法，
//其基本原理是：两个整数 a 和 b（a > b）的最大公约数等于 b 和 a% b 的最大公约数。
//不断重复这个过程，直到余数为 0，此时的除数就是最大公约数。
//*/
//
//#include <stdio.h>
//
//// 函数用于计算两个数的最大公约数
//int gcd(int a, int b) 
//{
//    int temp;
//    while (b != 0)
//    {
//        temp = b;
//        b = a % b;
//        a = temp;
//    }
//    return a;
//}
//
//int main()
//{
//    int num1, num2;
//    printf("请输入两个整数: ");
//    scanf("%d %d", &num1, &num2);
//
//    int result = gcd(num1, num2);
//    printf("%d 和 %d 的最大公约数是 %d\n", num1, num2, result);
//
//    return 0;
//}


///*
//方法二：更相减损术
//更相减损术是中国古代的一种求最大公约数的算法，
//其基本思想是：两个正整数 a 和 b（a > b），它们的最大公约数等于 a - b 和 b 的最大公约数。
//重复这个过程，直到两个数相等，此时这个数就是最大公约数。
//*/
//
//#include <stdio.h>
//
//// 函数用于计算两个数的最大公约数
//int gcd(int a, int b) 
//{
//    while (a != b) 
//    {
//        if (a > b) 
//        {
//            a = a - b;
//        }
//        else 
//        {
//            b = b - a;
//        }
//    }
//    return a;
//}
//
//int main() 
//{
//    int num1, num2;
//    printf("请输入两个整数: ");
//    scanf("%d %d", &num1, &num2);
//
//    int result = gcd(num1, num2);
//    printf("%d 和 %d 的最大公约数是 %d\n", num1, num2, result);
//
//    return 0;
//}


///*
//方法三：穷举法
//穷举法的基本思路是从两个数中较小的数开始，依次递减，
//直到找到一个能同时整除这两个数的数，这个数就是最大公约数。
//*/
//
//#include <stdio.h>
//
//// 函数用于计算两个数的最大公约数
//int gcd(int a, int b) 
//{
//    int min;
//    if (a < b) 
//    {
//        min = a;
//    }
//    else 
//    {
//        min = b;
//    }
//
//    while (1) 
//    {
//        if (a % min == 0 && b % min == 0) 
//        {
//            break;
//        }
//        min--;
//    }
//    return min;
//}
//
//int main() 
//{
//    int num1, num2;
//    printf("请输入两个整数: ");
//    scanf("%d %d", &num1, &num2);
//
//    int result = gcd(num1, num2);
//    printf("%d 和 %d 的最大公约数是 %d\n", num1, num2, result);
//
//    return 0;
//}


///*
//Stein 算法（二进制算法）
//Stein 算法主要是针对辗转相除法在处理大整数时取模运算效率较低的问题进行优化。
//它利用了二进制移位操作，避免了大整数的取模运算，从而提高了计算效率。
//*/
//
//#include <stdio.h>
//
//// 函数用于计算两个数的最大公约数
//int gcd(int a, int b) {
//    if (a == 0) return b;
//    if (b == 0) return a;
//
//    int shift = 0;
//    // 先找出 a 和 b 中公共的 2 的因子
//    while (((a | b) & 1) == 0) {
//        a >>= 1;
//        b >>= 1;
//        shift++;
//    }
//
//    // 去掉 a 中单独的 2 的因子
//    while ((a & 1) == 0) {
//        a >>= 1;
//    }
//
//    do {
//        // 去掉 b 中单独的 2 的因子
//        while ((b & 1) == 0) {
//            b >>= 1;
//        }
//
//        if (a > b) {
//            int temp = a;
//            a = b;
//            b = temp;
//        }
//        b = b - a;
//    } while (b != 0);
//
//    // 最后将之前提取的 2 的因子乘回去
//    return a << shift;
//}
//
//int main() {
//    int num1, num2;
//    printf("请输入两个整数: ");
//    scanf("%d %d", &num1, &num2);
//
//    int result = gcd(num1, num2);
//    printf("%d 和 %d 的最大公约数是 %d\n", num1, num2, result);
//
//    return 0;
//}


///*
// 递归形式的辗转相除法
//辗转相除法除了可以用迭代实现，还可以使用递归的方式来实现，代码更加简洁。
//*/
//
//#include <stdio.h>
//
//// 递归函数用于计算两个数的最大公约数
//int gcd(int a, int b) {
//    if (b == 0) {
//        return a;
//    }
//    return gcd(b, a % b);
//}
//
//int main() {
//    int num1, num2;
//    printf("请输入两个整数: ");
//    scanf("%d %d", &num1, &num2);
//
//    int result = gcd(num1, num2);
//    printf("%d 和 %d 的最大公约数是 %d\n", num1, num2, result);
//
//    return 0;
//}